package com.linyaonan.leetcode.medium._437;


import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 *
 * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
 * 输出：3
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/path-sum-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {

    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefix = new HashMap<>();
        prefix.put(0L, 1);
        return dfs(root, prefix, 0, targetSum);
    }

    public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = 0;
        curr += root.val;

        ret = prefix.getOrDefault(curr - targetSum, 0);
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
        ret += dfs(root.left, prefix, curr, targetSum);
        ret += dfs(root.right, prefix, curr, targetSum);
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);

        return ret;
    }

    HashMap<Long, Integer> sumMap = new HashMap<>();

    int su = 0;

    public int pathSum2(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        sumMap.put(0L, 1);
        getSum(root, 0L, targetSum);

        return su;
    }

    private void getSum(TreeNode root, long cur, int t) {
        if (root != null) {
            cur += root.val;
            su += sumMap.getOrDefault(cur - t, 0);
            sumMap.merge(cur, 1, Integer::sum);
            getSum(root.left, cur, t);
            getSum(root.right, cur, t);
            sumMap.merge(cur, -1, Integer::sum);
        }
    }

}